package com.jxb.first;

/**
 *  删除排序链表中的重复元素
 */
public class RemoveDuplicates {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode();
        listNode1.val = 1;
        ListNode listNode2 = new ListNode();
        listNode2.val = 2;
        ListNode listNode3 = new ListNode();
        listNode3.val = 2;
        ListNode listNode4 = new ListNode();
        listNode4.val = 3;
        listNode4.next = null;
        listNode3.next = listNode4;
        listNode2.next = listNode3;
        listNode1.next = listNode2;
//        ListNode listNode = removeDuplicatesNode(listNode1);
        ListNode listNode = deleteDuplicatesRecursive(listNode1);
        System.out.println(listNode);
    }

    //循环遍历，时间复杂度为O(n),空间复杂度为O(1)
    public static ListNode removeDuplicatesNode(ListNode listNode) {
        if (listNode == null) {
            return listNode;
        }
        ListNode currentNode = listNode;
        while (currentNode.next != null) {
            if (currentNode.val == currentNode.next.val) {
                currentNode.next = currentNode.next.next;
            }else {
                currentNode = currentNode.next;
            }
        }
        return listNode;
    }

    //倒序递归-时间复杂度：O(n)，空间复杂度：O(n)
    public static ListNode deleteDuplicatesRecursive(ListNode listNode) {
        if (listNode == null || listNode.next == null) {
            return listNode;
        }
        listNode.next = deleteDuplicatesRecursive(listNode.next);
        if (listNode.val == listNode.next.val) {
            return listNode.next;
        }else {
            return listNode;
        }
    }

}
